#include <stdlib.h>
#include <stdio.h>

#define maxSize 100
#define INF 0xffff

//定点定义
typedef struct
{
    int no;   //顶点编号
    char info; //顶点其他信息
} VertexType; //顶点类型

typedef struct
{   //邻接矩阵的定义
    int edges[maxSize][maxSize];
    int n, e; //顶点数， 边数
    VertexType vex[maxSize]; //存放节点信息
}MGraph;

//邻接表
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextArc;
    int info;
}ArcNode;

typedef struct
{
    char data;
    ArcNode * firstarc;
}VNode;

typedef struct
{
    VNode adjlist[maxSize]; // 邻接表
    int n,e;   // 顶点数和边数
}*AGraph;


//DFS
int visit[maxSize];  //用于记录访访问过的节点避免回路。
void DFS(AGraph G, int v){
    ArcNode *arc = G->adjlist[v].firstarc;
    visit[v] = 1;
    //action();
    while (arc != NULL){
        if(visit[arc->adjvex] == 0){
            DFS(G, v);
        }
        arc = arc->nextArc;
    }
}

//BFS
void BFS(AGraph G, int v, int visit[maxSize]){
    int queue[maxSize], front = 0, rear = 0; //队列
    visit[v] = 1;
    rear = (rear + 1)%maxSize;
    queue[rear] = v;

    ArcNode *arc;
    while(rear != front){
        front = (front + 1)%maxSize;
        v = queue[front];
        //action();
        arc = G->adjlist[v].firstarc;
        while(arc != NULL){
            if(visit[arc->adjvex] == 0){
                rear = (rear + 1)%maxSize;
                queue[rear] = arc->adjvex;
            }
            arc = arc->nextArc;
        }
    }
}



//最小生成树
//普里姆算法
/*
 * 从图中任取一个顶点，以这个顶点为树，然后从颗树所有节点的边中找到权值最小的边
 * 将这个边，和边对应的点并入树中，直到将所有的点都并入
*/
int Prim(MGraph g, int vertex){
    int lowcost[maxSize], vertexSet[maxSize];
    int newVertex;
    //初始化 lowcost, vettexSet, newVerTex
    for (int i = 0; i < g.n; ++i) {
        lowcost[i] = g.edges[vertex][i];
        vertexSet[i] = 0;
    }
    vertexSet[vertex] = 1;
    int sum = 0;
    //主逻辑
    for (int i = 0; i < g.n; ++i) {
        int min = INF;
        //在剩余顶点中找到最短路径的
        for (int j = 0; j < g.n; ++j) {
            if(vertexSet[j] == 0 && lowcost[j] < min){
                min = lowcost[j];
                newVertex = j;
            }
            vertexSet[newVertex] = 1;
            sum += min;
        }
        //更新 lowcost
        for (int j = 0; j < g.n; ++j) {
            if(vertexSet[j] == 0 && lowcost[j] > g.edges[newVertex][j]){
                lowcost[j] = g.edges[newVertex][j];
            }
        }
    }
    return sum;
}

//克鲁斯卡尔算法
/*
 *找到候选权值最小的边，并将该边并入生成树中。重复过程知道
*/
typedef struct
{
    int v1, v2; //一条边所连的两条顶点
    int w;      //边的权值
}Road;


int getRoot(int vertex, int disjointSet[]){  //找到根节点
    while (vertex != disjointSet[vertex]){
        vertex = disjointSet[vertex];
    }
    return vertex;
}
int comp(const void*a, const void*b){
    return ((Road*)a)->w > ((Road*)b)->w ;
}

int  Kruskal(MGraph g){
    //初始化
    int N = g.n, E = g.e;
    int v1, v2;
    int sum = 0;
    Road road[maxSize];       //
    int disjointSet[maxSize]; //定义并查集
    for(int i = 0; i < N; i++){
        disjointSet[i] = i;
    }
    //对数组中的每条边按权值大小排序
    qsort(road, maxSize, sizeof(int), comp);
    for (int j = 0; j < E; ++j) {
        v1 = getRoot(road[j].v1, disjointSet);
        v2 = getRoot(road[j].v2, disjointSet);
        if(v1 != v2){
            disjointSet[v1] = v2;
            sum += road[j].w;
        }
    }
}


//输出从原点到顶点的最短路径
void printfDijketraPath(int path[], int vertex){
    int stack[maxSize], top = -1;
    while(path[vertex] != -1){
        top += 1;
        stack[top] = vertex;
        vertex = path[vertex];
    }
    top += 1;
    stack[top] = vertex;
    while(top != 1){
        printf("%d", top);
        top--;
    }
}

void Dijkstra(MGraph g, int source, int *dist, int *path){
    int set[maxSize], min, u;
    //初始化
    for(int i = 0; i < g.n; i++){
        set[i] = 0;
        dist[i] = g.edges[source][i];
        if(g.edges[source][i] < INF){
            path[i] = source;
        } else{
            path[i] = -1;
        }
    }
    set[source] = 1;
    path[source] = -1;
    for(int i = 0; i < g.n-1; i++){
        //找到最短路径的节点
        min = INF;
        for(int j = 1; j < g.n; i++){
            if(set[j] == 0 && dist[j] < min ){
                min = dist[j];
                u = j;
            }
        }
        set[u] = 1;
        int uDict = dist[u];
        for(int j = 1; j < g.n; j++){
            if((set[j] == 0) && (uDict + g.edges[u][j] < dist[j])){
                path[j] = u;
                dist[j] = uDict + g.edges[u][j];
            }
        }
    }
}

MGraph create_map(){
    int n = 7;
    int e = -1;
    int edges[7][7] = {{}, {3, 4}};
}

//弗洛伊德算法
//输出两点之间的最短路径
void printfFloydPath(int start, int end, int path[][maxSize]){
    if(path[start][end] == -1){
        printf("%d");
    } else{
        int mid = path[start][end];
        printfFloydPath(start, mid, path); //处理前半段路径
        printfFloydPath(mid, end, path); // 处理后半段路径
    }
}

void Floyd(MGraph g, int path[][MAX_PATH]){
    int i, j;
    int A[maxSize][maxSize];
    //对数组a[][], Path[][] 进行初始化，
    for(i = 1; i < g.n; ++i){
        for (j = 0; j < g.n; ++j) {
            A[i][j] = g.edges[i][j];
            path[i][j] = -1;
        }
    }
    //完成以k为中间点对所有的顶点对{i, j}进行检测和修改
    for (int k = 0; k < g.n; ++k) {
        for (i = 0; i < g.n; ++i) {
            for (j = 0; j < g.n; ++j) {
                if(A[i][j] > A[i][k] + A[k][j]){
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] =  k;
                }
            }
        }
    }
}

